package com.example.tree.segmenttree;

import java.util.Arrays;

/**
 * 给你一个数组 nums ，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。
 *
 *  实现 NumArray 类：
 *
 *  NumArray(int[] nums) 用整数数组 nums 初始化对象
 *  void update(int index, int val) 将 nums[index] 的值更新为 val
 *  int sumRange(int left, int right) 返回子数组 nums[left, right] 的总和（即，nums[left] +
 * nums[left + 1], ..., nums[right]）

 * 示例：
 * 输入：
 * ["NumArray", "sumRange", "update", "sumRange"]
 * [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
 * 输出：
 * [null, 9, null, 8]
 *
 * 解释：
 * NumArray numArray = new NumArray([1, 3, 5]);
 * numArray.sumRange(0, 2); // 返回 9 ，sum([1,3,5]) = 9
 * numArray.update(1, 2);   // nums = [1,2,5]
 * numArray.sumRange(0, 2); // 返回 8 ，sum([1,2,5]) = 8
 */
public class Leetcode307_NumArray {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5};
        NumArray numArray = new NumArray(nums);
        System.out.println(numArray.sumRange(0,2));
        numArray.update(1, 2);
        System.out.println(numArray.sumRange(0, 2));

    }

    /**
     * 解法一:线段树(递归实现)
     */
    static class NumArrayByRecursion {
        private int len;
        private int[] nums;
        private int[] treeNodes;

        public NumArrayByRecursion(int[] nums) {
            len = nums.length;
            this.nums = Arrays.copyOf(nums, len);
            treeNodes = new int[4 * len];
            if (len > 0) {
                buildTree(0, 0, len - 1);
            }
        }

        public void update(int i, int val) {
            updateSingle(0, 0, len - 1, i, val);
            nums[i] = val;
        }

        public int sumRange(int i, int j) {
            if (i > j || j < 0 || i >= len) {
                return 0;
            }
            return queryTree(0, 0, len - 1, i, j);
        }

        private void buildTree(int root, int l, int r) {
            if (l == r) {
                treeNodes[root] = nums[l];
                return;
            }
            int mid = (l + r) / 2;
            buildTree(2 * root + 1, l, mid);
            buildTree(2 * root + 2, mid + 1, r);
            treeNodes[root] = treeNodes[2 * root + 1] + treeNodes[2 * root + 2];
        }

        private int queryTree(int root, int left, int right, int ql, int qr) {
            if (ql > right || qr < left) {
                return 0;
            }
            if (left >= ql && right <= qr) {
                return treeNodes[root];
            }
            int mid = (left + right) / 2;
            return queryTree(2 * root + 1, left, mid, ql, qr)
                    + queryTree(2 * root + 2, mid + 1, right, ql, qr);
        }

        private void updateSingle(int root, int left, int right, int i, int newValue) {
            if (left == right && left == i) {
                treeNodes[root] = newValue;
                return;
            }
            if (i < left || i > right) {
                return;
            }
            int mid = (left + right) / 2;
            updateSingle(2 * root + 1, left, mid, i, newValue);
            updateSingle(2 * root + 2, mid + 1, right, i, newValue);
            treeNodes[root] = treeNodes[2 * root + 1] + treeNodes[2 * root + 2];
        }

    }

    /**
     * 线段树(迭代实现)
     */
    static class NumArray {

        int[] treeNodes;
        int n;

        public NumArray(int[] nums) {
            if (nums.length > 0) {
                n = nums.length;
                treeNodes = new int[n * 2];
                // 把原数组拷贝到新数组的后半部分
                System.arraycopy(nums, 0, treeNodes, 0 + n, n);
                //计算区域和
                for (int i = n - 1; i > 0; i--) {
                    treeNodes[i] = treeNodes[i * 2] + treeNodes[i * 2 + 1];
                }
            }
        }

        public void update(int pos, int val) {
            pos = pos + n;
            //更新叶节点值
            treeNodes[pos] = val;
            pos /= 2;
            while (pos > 0) {
                //更新父节点值
                treeNodes[pos] = treeNodes[pos * 2] + treeNodes[pos * 2 + 1];
                pos /= 2;
            }
        }

        public int sumRange(int left, int right) {
            left += n;
            right += n;
            int sum = 0;
            while (left <= right) {
                //判断左索引节点是否是父节点的右子节点
                if ((left % 2) == 1) {
                    sum += treeNodes[left];
                    left++;
                }
                //判断右索引节点是否是父节点的左子节点
                if ((right % 2) == 0) {
                    sum += treeNodes[right];
                    right--;
                }
                left /= 2;
                right /= 2;
            }
            return sum;
        }
    }
}
